package com.LeetCode.String;

import java.util.LinkedList;
import java.util.Queue;

/**
 * AC自动机
 */
public class ACAutoMatch {



    private class ACNode{
        public char data;
        public ACNode[] children = new ACNode[26];//孩子节点
        public boolean isEnd = false;//结束标志
        public int len;
        public ACNode fail;//失败指针
        public ACNode(char data){
            this.data = data;
        }
    }

    public ACNode root;

    public ACAutoMatch(String[] strs){
        root = new ACNode('/');
        for(String str : strs)
            InitInsert(str.toLowerCase());

        //全部插入完了再来构建失败指针
        buildFailNode();
    }

    /**
     * 插入新的敏感词
     * @param str
     */
    public void insert(String str){
        char[] chars = str.toCharArray();
        ACNode cur = root;

        for(int i = 0; i<chars.length; i++){
            if(cur.children[chars[i] - 'a'] == null){
                cur.children[chars[i] - 'a'] = new ACNode(chars[i]);
            }
            cur = cur.children[chars[i] - 'a'];
        }
        cur.isEnd = true;
        cur.len = chars.length;

        //重新构建失败指针
        buildFailNode();
    }

    /**
     * 初始化阶段插入的敏感词
     * @param str
     */
    public void InitInsert(String str){
        char[] chars = str.toCharArray();
        ACNode cur = root;

        for(int i = 0; i<chars.length; i++){
            if(cur.children[chars[i] - 'a'] == null){
                cur.children[chars[i] - 'a'] = new ACNode(chars[i]);
            }
            cur = cur.children[chars[i] - 'a'];
        }
        cur.isEnd = true;
        cur.len = chars.length;

        //避免多次重新构建失败指针，所以这里直接结束调用
    }

    /**
     * 构建失败指针
     */
    public void buildFailNode(){
        Queue<ACNode> queue = new LinkedList<>();
        root.fail = null;
        queue.offer(root);
        while(!queue.isEmpty()){
            ACNode cur = queue.poll();
            for(int i = 0; i<26; i++){
                ACNode cur_child = cur.children[i];
                if(cur_child == null) continue;
                if(cur == root){
                    cur_child.fail = root;//第一层节点的 fail 指针默认指向 root
                }
                else{//从第二层开始的节点
                    ACNode cur_fail = cur.fail;
                    while(cur_fail != null){
                        ACNode cur_fail_child = cur_fail.children[cur_child.data - 'a'];
                        if(cur_fail_child != null){
                            cur_child.fail = cur_fail_child;
                            break;
                        }
                        cur_fail = cur_fail.fail;
                    }
                    if(cur_fail == null){
                        cur_child.fail = root;
                    }
                }
                queue.offer(cur_child);
            }
        }
    }

    /**
     * 判断一个词是否是敏感词
     * @param str
     * @return
     */
    public boolean Match(String str){
        char[] chars = str.toCharArray();
        ACNode cur = root;
        for(int i = 0; i<chars.length; i++){
            ACNode nextNode = cur.children[chars[i] - 'a'];
            if(nextNode == null)
                return false;
            cur = nextNode;
        }
        return cur.isEnd;
    }



    /**
     * 过滤敏感词
     * @param str 用户输入的文本
     * @return
     */
    public String filterStr(String str){
        char[] chars = str.toCharArray();
        int len = chars.length;
        ACNode cur = root;
        StringBuilder strb = new StringBuilder();
        for(int i = 0; i<len; i++){
            int index = chars[i] - 'a';

            while(cur.children[index] == null && cur != root){
                cur = cur.fail;
            }

            strb.append(chars[i]);
            if(cur.children[index]!=null){

                if(cur.children[index].isEnd){
                    strb.delete(strb.length() - cur.children[index].len , strb.length());
                    strb.append(fits[cur.children[index].len]);
                }

//                System.out.println(cur.children[index].data
//                        + " " + cur.children[index].isEnd
//                        + " "+ cur.children[index].len);
                cur = cur.children[index];
            }
        }
        return strb.toString();
    }

    /**
     * 提前构造好替换的字符串
     */
    String[] fits = {"", "*", "**", "***", "****", "*****",
            "******", "*******", "********", "*********",
            "**********", "***********", "************", "*************",
            "**************", "***************", "****************", "*****************",
            "******************", "*******************", "********************",
            "*********************", "**********************", "***********************", "" +
            "************************", "*************************", "**************************",
            "***************************", "****************************", "*****************************",
            "******************************", "*******************************",
            "********************************",};


    public static void main(String[] args) {
        String[] strs = {"fuck","piepiper","penis","dick"};
        ACAutoMatch acAutoMatch = new ACAutoMatch(strs);

        System.out.println(acAutoMatch.filterStr("fucfuckfffhadjksfpiepiepiperpppiepiper"));
        System.out.println(acAutoMatch.filterStr("fucfuckpeipiperppfnkels"));

        acAutoMatch.insert("fuc");

        System.out.println(acAutoMatch.filterStr("fucfuckfffhadjksfpiepiepiperpppiepiper"));
        System.out.println(acAutoMatch.filterStr("fucfuckpeipiperppfnkels"));


    }

}































